from collections import deque
from typing import Optional
from python.mypackage import TreeNode


class Solution:

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node: Optional[TreeNode], depth: int) -> None:
            if node is None:
                return
            if depth == len(ans):
                ans.append(node.val)
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        dfs(root, 0)
        return ans
     
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        rightmost_value_at_depth = dict()
        max_depth = -1
        queue = deque([(root, 0)])
        while(queue):
            node, depth = queue.popleft()
            if node is not None:
                max_depth = max(max_depth, depth)
                rightmost_value_at_depth[depth] = node.val
                queue.append((node.left, depth + 1))
                queue.append((node.right, depth + 1))
        return [rightmost_value_at_depth[depth] for depth in range(max_depth + 1)]